package cn.edu.zufe.mjt.dp;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 动态规划 —— 前缀和问题
 * 给定一个长度为n的整数序列a1,a2,…,an,要求计算并输出每个前缀的和，即求出:
 * S=a1+a2+a3+…+an
 */
public class PrefixSumQuestions {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        System.out.println(Arrays.toString(prefixSum2(a)));
    }

    /**
     * 令：
     * Si= a1+ a2+…+ai
     * 显然:
     * S(i-1)=a1+a2+…+a(i-1)
     * Si= S(i-1)+ ai
     */
    public static int[] prefixSum(int[] a) {
        int n = a.length;
        int[] prefixSum = new int[n];
        prefixSum[0] = a[0];
        for (int i = 1; i < n; i++) {
            prefixSum[i] = prefixSum[i - 1] + a[i];
        }
        return prefixSum;
    }
    // 优化版，滚动数组
    public static int[] prefixSum2(int[] a) {
        int n = a.length;
        for (int i = 1; i < n; i++) {
            a[i] += a[i - 1];
        }
        return a;
    }
}
